{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check If Two Expression Trees are Equivalent"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkEquivalence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #检查两棵二叉表达式树是否等价"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong><a href=\"https://en.wikipedia.org/wiki/Binary_expression_tree\" target=\"_blank\">二叉表达式树</a></strong>是一种表达算术表达式的二叉树。二叉表达式树中的每一个节点都有零个或两个子节点。&nbsp;叶节点（有 0 个子节点的节点）表示操作数，非叶节点（有 2 个子节点的节点）表示运算符。在本题中，我们只考虑 <code>'+'</code> 运算符（即加法）。</p>\n",
    "\n",
    "<p>给定两棵二叉表达式树的根节点&nbsp;<code>root1</code>&nbsp;和&nbsp;<code>root2</code>&nbsp;。<em>如果两棵二叉表达式树等价</em>，返回&nbsp;<code>true</code>&nbsp;，否则返回&nbsp;<code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>当两棵二叉搜索树中的变量取任意值，<strong>分别求得的值都相等</strong>时，我们称这两棵二叉表达式树是等价的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b> root1 = [x], root2 = [x]\n",
    "<b>输出：</b> true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/04/tree1.png\" style=\"width: 211px; height: 131px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>root1 = [+,a,+,null,null,b,c], root2 = [+,+,a,b,c]\n",
    "<b>输出：</b>true\n",
    "<code><span style=\"\"><b>解释：</b></span>a + (b + c) == (b + c) + a</code></pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/04/tree2.png\" style=\"width: 211px; height: 131px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b> root1 = [+,a,+,null,null,b,c], root2 = [+,+,a,b,d]\n",
    "<b>输出：</b> false\n",
    "<b>解释：</b> <code>a + (b + c) != (b + d) + a</code>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>两棵树中的节点个数相等，且节点个数为范围&nbsp;<code>[1, 4999]</code>&nbsp;内的奇数。</li>\n",
    "\t<li><code>Node.val</code>&nbsp;是&nbsp;<code>'+'</code>&nbsp;或小写英文字母。</li>\n",
    "\t<li>给定的树<strong>保证</strong>是有效的二叉表达式树。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>进阶：</b>当你的答案需同时支持&nbsp;<code>'-'</code>&nbsp;运算符（减法）时，你该如何修改你的答案</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-if-two-expression-trees-are-equivalent](https://leetcode.cn/problems/check-if-two-expression-trees-are-equivalent/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-if-two-expression-trees-are-equivalent](https://leetcode.cn/problems/check-if-two-expression-trees-are-equivalent/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[x]\\n[x]', '[+,a,+,null,null,b,c]\\n[+,+,a,b,c]', '[+,a,+,null,null,b,c]\\n[+,+,a,b,d]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class Node(object):\n",
    "#     def __init__(self, val=\" \", left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEquivalence(self, root1: 'Node', root2: 'Node') -> bool:\n",
    "        def dfs(root):\n",
    "            temp=[0]*26\n",
    "            if root==None:\n",
    "                return temp\n",
    "            templeft=dfs(root.left)\n",
    "            tempright=dfs(root.right)\n",
    "            for i in range(26):\n",
    "                temp[i]=templeft[i]+tempright[i]\n",
    "            if root.val!='+':\n",
    "                temp[ord(root.val)-ord('a')]+=1\n",
    "            return temp\n",
    "        return dfs(root1)==dfs(root2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class Node(object):\n",
    "#     def __init__(self, val=\" \", left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEquivalence(self, root1: 'Node', root2: 'Node') -> bool:\n",
    "        d0, d1 = defaultdict(int), defaultdict(int)\n",
    "        def dfs(root, dic):\n",
    "            if root is None: return root\n",
    "            dfs(root.left, dic)\n",
    "            dfs(root.right, dic)\n",
    "            if root.val != '+':\n",
    "                dic[root.val] += 1\n",
    "        dfs(root1, d0)\n",
    "        dfs(root2, d1)\n",
    "        if len(d0) != len(d1):\n",
    "            return False\n",
    "        for k, v in d0.items():\n",
    "            if k not in d1 or d1[k] != v:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkEquivalence(self, root1: 'Node', root2: 'Node') -> bool:\n",
    "        \n",
    "        # DFS function to collect all operands in a tree\n",
    "        def dfs(node, operands):\n",
    "            if not node:\n",
    "                return\n",
    "            if not node.left and not node.right:\n",
    "                operands.append(node.val)\n",
    "            else:\n",
    "                dfs(node.left, operands)\n",
    "                dfs(node.right, operands)\n",
    "\n",
    "        # Get operands for both trees\n",
    "        operands1 = []\n",
    "        operands2 = []\n",
    "        dfs(root1, operands1)\n",
    "        dfs(root2, operands2)\n",
    "        \n",
    "        # Sort and compare the operands\n",
    "        return sorted(operands1) == sorted(operands2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class Node(object):\n",
    "#     def __init__(self, val=\" \", left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEquivalence(self, root1: 'Node', root2: 'Node') -> bool:\n",
    "        cnt = collections.defaultdict(int)\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return\n",
    "            if root.val != '+':\n",
    "                cnt[root.val] += 1\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root1)\n",
    "        for k in cnt:\n",
    "            cnt[k] *= -1\n",
    "        dfs(root2)\n",
    "        return all(v == 0 for v in cnt.values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class Node(object):\n",
    "#     def __init__(self, val=\" \", left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEquivalence(self, root1: 'Node', root2: 'Node') -> bool:\n",
    "        def bfs(root):\n",
    "            Q = deque([root])\n",
    "            res = [0]*26\n",
    "            while Q:\n",
    "                node = Q.pop()\n",
    "                if node.val != '+':\n",
    "                    res[ord(node.val) - ord('a')] += 1\n",
    "                    continue\n",
    "                Q.appendleft(node.left)\n",
    "                Q.appendleft(node.right)\n",
    "            return res\n",
    "        \n",
    "        return bfs(root1) == bfs(root2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class Node(object):\n",
    "#     def __init__(self, val=\" \", left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEquivalence(self, root1: 'Node', root2: 'Node') -> bool:\n",
    "        res1 = list()\n",
    "        res2 = list()\n",
    "\n",
    "        def dfs(root, res):\n",
    "            if root is None:\n",
    "                return\n",
    "            if root.left is None and root.right is None:\n",
    "                res.append(root.val)\n",
    "                return\n",
    "            dfs(root.left, res)\n",
    "            dfs(root.right, res)\n",
    "\n",
    "        dfs(root1, res1)\n",
    "        dfs(root2, res2)\n",
    "        res1.sort()\n",
    "        res2.sort()\n",
    "        return res1 == res2\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class Node(object):\n",
    "#     def __init__(self, val=\" \", left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEquivalence(self, root1: 'Node', root2: 'Node') -> bool:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return []\n",
    "            return dfs(root.left) + [root.val] + dfs(root.right)\n",
    "\n",
    "        temp1 = dfs(root1)\n",
    "        temp2 = dfs(root2)\n",
    "        # print(temp1, temp2)\n",
    "        return sorted(temp1) == sorted(temp2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class Node(object):\n",
    "#     def __init__(self, val=\" \", left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEquivalence(self, root1: 'Node', root2: 'Node') -> bool:\n",
    "        return self.dfs(root1) == self.dfs(root2)\n",
    "    def dfs(self, rt: 'Node') -> List[int]:\n",
    "        if rt == None:\n",
    "            return [0 for _ in range(26)]\n",
    "        if rt.left == None and rt.right == None:\n",
    "            res = [0 for _ in range(26)]\n",
    "            idx = ord(rt.val) - ord('a')\n",
    "            res[idx] = 1\n",
    "            return res \n",
    "        L = self.dfs(rt.left)\n",
    "        R = self.dfs(rt.right)\n",
    "        return [L[i] + R[i] for i in range(26)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class Node(object):\r\n",
    "#     def __init__(self, val=\" \", left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def checkEquivalence(self, root1: 'Node', root2: 'Node') -> bool:\r\n",
    "        return self.dfs(root1) == self.dfs(root2)   \r\n",
    "\r\n",
    "    #### 统计树rt各个字母的个数\r\n",
    "    def dfs(self, rt: 'Node') -> List[int]:\r\n",
    "        ## 空结点\r\n",
    "        if rt == None:\r\n",
    "            return [0 for _ in range(26)]\r\n",
    "        ## 叶结点\r\n",
    "        if rt.left == None and rt.right == None:\r\n",
    "            res = [0 for _ in range(26)]\r\n",
    "            idx = ord(rt.val) - ord('a')\r\n",
    "            res[idx] = 1\r\n",
    "            return res\r\n",
    "        ## 非叶结点\r\n",
    "        L = self.dfs(rt.left)\r\n",
    "        R = self.dfs(rt.right)\r\n",
    "        return [ L[i]+R[i] for i in range(26)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class Node(object):\n",
    "#     def __init__(self, val=\" \", left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEquivalence(self, root1: 'Node', root2: 'Node') -> bool:\n",
    "        dict1 = {}\n",
    "        stack = [root1]\n",
    "        while stack:\n",
    "            i = stack.pop()\n",
    "            x = i.val\n",
    "            if x == '+':\n",
    "                stack.append(i.left)\n",
    "                stack.append(i.right)\n",
    "            else:\n",
    "                if x in dict1:\n",
    "                    dict1[x] += 1\n",
    "                else:\n",
    "                    dict1[x] = 1\n",
    "        dict2 = {}\n",
    "        stack = [root2]\n",
    "        while stack:\n",
    "            i = stack.pop()\n",
    "            x = i.val\n",
    "            if x == '+':\n",
    "                stack.append(i.left)\n",
    "                stack.append(i.right)\n",
    "            else:\n",
    "                if x in dict2:\n",
    "                    dict2[x] += 1\n",
    "                else:\n",
    "                    dict2[x] = 1\n",
    "        return dict1 == dict2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class Node(object):\n",
    "#     def __init__(self, val=\" \", left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def checkEquivalence(self, root1: 'Node', root2: 'Node') -> bool:\n",
    "        def dfs(root,dic):\n",
    "            if not root:\n",
    "                return\n",
    "            if 97 <= ord(root.val) <= 122:\n",
    "                dic[root.val] += 1\n",
    "            dfs(root.left,dic)\n",
    "            dfs(root.right,dic)\n",
    "            return dic\n",
    "        return dfs(root1,defaultdict(int)) == dfs(root2,defaultdict(int))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
